#include <stdio.h>
#include <math.h>

struct SchemeElem
{
	int exist;
	int vector_length;
	int vector_value[32];
	int positive_pointer;
	int negative_pointer;
	int fictive_variable;
	int to_null;
	int absolute_node_num;
	int absolute_positive_pointer;
	int absolute_negative_pointer;
	int variable_number;
};

struct KascadeMatrix
{
	int exist;
	int variable_number;
	int is_inverse;
};

SchemeElem scheme[6][32];
KascadeMatrix ContactScheme[256][256];

int SchemeNodeNum;
int SchemeEdgeNum;

int make_kascade(int function_vector[32])
{
	int i,j;
	
	int kaskade_level,upper_level_node,k,lower_level_node;
	int node_num;

	int positive_temporary_vector[32], negative_temporary_vector[32];
	int temporary_length;

	bool positive_subfunction_flag, negative_subfunction_flag, function_equvalence, negative_break, positive_break;

	SchemeNodeNum = 0;
	SchemeEdgeNum = 0;

	//allocate each scheme level 
	node_num = 1;
	temporary_length = 32;
	for (kaskade_level = 0; kaskade_level < 5; kaskade_level++)
	{
		//clear information
		for(j = 0; j <= node_num; j++)
		{
			scheme[kaskade_level][j].exist = 0;
			scheme[kaskade_level][j].fictive_variable = 0;
			scheme[kaskade_level][j].positive_pointer = -1;
			scheme[kaskade_level][j].negative_pointer = -1;
			scheme[kaskade_level][j].to_null = 0;
			scheme[kaskade_level][j].absolute_node_num = -1;
			scheme[kaskade_level][j].absolute_positive_pointer = -1;
			scheme[kaskade_level][j].absolute_negative_pointer = -1;
			scheme[kaskade_level][j].variable_number = -1;
			scheme[kaskade_level][j].vector_length = temporary_length;
		}
		node_num = node_num << 1;
		temporary_length = temporary_length >> 1;
	}

	for(j = 0; j <= 3; j++)
	{
		scheme[5][j].exist = 0;
		scheme[5][j].fictive_variable = 0;
		scheme[5][j].positive_pointer = -1;
		scheme[5][j].negative_pointer = -1;
		scheme[5][j].to_null = 0;
		scheme[5][j].absolute_node_num = -1;
		scheme[5][j].absolute_positive_pointer = -1;
		scheme[5][j].absolute_negative_pointer = -1;
		scheme[5][j].variable_number = -1;
		scheme[5][j].vector_length = 1;
	}

	//create first node (final function point)
	scheme[0][0].exist = 1;
	scheme[0][0].vector_length = 32;
	for(i = 0; i < 32; i++)
	{
		scheme[0][0].vector_value[i] = function_vector[i];
	}

	//constructing sets of nodes for each of kascade level
	for(kaskade_level = 1; kaskade_level <= 5; kaskade_level++)
	{
		upper_level_node = 0;
		//for each element in the upper kascade level (already constructed level)
		while(scheme[kaskade_level-1][upper_level_node].exist)
		{
			temporary_length = scheme[kaskade_level][upper_level_node].vector_length;
			
			//take the subfunctions
			for(k = 0; k < temporary_length; k++)
			{
				negative_temporary_vector[k] = scheme[kaskade_level-1][upper_level_node].vector_value[k];
				positive_temporary_vector[k] = scheme[kaskade_level-1][upper_level_node].vector_value[k+temporary_length];
			}

			negative_temporary_vector[k] = 255;
			positive_temporary_vector[k] = 255;

			//test of fictive variable
			function_equvalence = 1;
			for(k = 0; k < temporary_length; k++)
			{
				function_equvalence = (function_equvalence) && (positive_temporary_vector[k] == negative_temporary_vector[k]);
			}

			if (function_equvalence) //if this variable is fictive
			{
				scheme[kaskade_level-1][upper_level_node].fictive_variable = 1;
			}

			//add functions to the lower level or define already existing subfunctions
			positive_subfunction_flag = 0;
			negative_subfunction_flag = 0;
			negative_break = 0;
			positive_break = 0;
			lower_level_node = 0;
			while(scheme[kaskade_level][lower_level_node].exist)
			{
				function_equvalence = 1;
				for(k = 0; k < temporary_length; k++)
				{
					function_equvalence = (function_equvalence) && (scheme[kaskade_level][lower_level_node].vector_value[k] == negative_temporary_vector[k]);
				}
				negative_subfunction_flag = negative_subfunction_flag || function_equvalence;
					
				function_equvalence = 1;
				for(k = 0; k < temporary_length; k++)
				{
					function_equvalence = (function_equvalence) && (scheme[kaskade_level][lower_level_node].vector_value[k] == positive_temporary_vector[k]);
				}
				positive_subfunction_flag = positive_subfunction_flag || function_equvalence;

				if ((negative_subfunction_flag) && (!negative_break))
				{
					scheme[kaskade_level-1][upper_level_node].negative_pointer = lower_level_node;
					negative_break = true;
				}
				if ((positive_subfunction_flag) && (!positive_break))
				{
					scheme[kaskade_level-1][upper_level_node].positive_pointer = lower_level_node;
					positive_break = true;
				}
				//go to the next node
				lower_level_node++;
			}
			if (negative_subfunction_flag == 0)
			{
				scheme[kaskade_level-1][upper_level_node].negative_pointer = lower_level_node;
				scheme[kaskade_level][lower_level_node].exist = 1;
				
				for(k = 0; k < temporary_length; k++)
				{
					scheme[kaskade_level][lower_level_node].vector_value[k] = negative_temporary_vector[k];
				}
				lower_level_node++;
				if (scheme[kaskade_level-1][upper_level_node].fictive_variable == 0)
				{
					if (positive_subfunction_flag == 0)
					{
						scheme[kaskade_level-1][upper_level_node].positive_pointer = lower_level_node;
						scheme[kaskade_level][lower_level_node].exist = 1;

						for(k = 0; k < temporary_length; k++)
						{
							scheme[kaskade_level][lower_level_node].vector_value[k] = positive_temporary_vector[k];
						}
					}
				} 
				else
				{
					scheme[kaskade_level-1][upper_level_node].positive_pointer = lower_level_node - 1;
				}
			}
			else
			{
				if (positive_subfunction_flag == 0)
				{
					scheme[kaskade_level-1][upper_level_node].positive_pointer = lower_level_node;
					scheme[kaskade_level][lower_level_node].exist = 1;

					for(k = 0; k < temporary_length; k++)
					{
						scheme[kaskade_level][lower_level_node].vector_value[k] = positive_temporary_vector[k];
					}
				}
			}
			//go to the next node
			upper_level_node++;
		}
	}

	//counting edges going to null and estimating absolute node number
	lower_level_node = 0;
	while(scheme[5][lower_level_node].exist)
	{
		if (scheme[5][lower_level_node].vector_value[0] == 0)
		{
			scheme[5][lower_level_node].to_null = 1;
			scheme[5][upper_level_node].fictive_variable = 1;
		}
		if (scheme[5][lower_level_node].vector_value[0] != 0)
		{
			scheme[5][lower_level_node].absolute_node_num = SchemeNodeNum;
			SchemeNodeNum++;
		}
		lower_level_node++;
	}

	for(kaskade_level = 4; kaskade_level >= 0; kaskade_level--)
	{
		upper_level_node = 0;
		while(scheme[kaskade_level][upper_level_node].exist)
		{
			if ((scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].positive_pointer].to_null == 1) && (scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].negative_pointer].to_null == 1))
			{
				scheme[kaskade_level][upper_level_node].to_null = 1;
				scheme[kaskade_level][upper_level_node].fictive_variable = 1;
			}
			if ((scheme[kaskade_level][upper_level_node].to_null != 1) && (scheme[kaskade_level][upper_level_node].fictive_variable != 1))
			{
				scheme[kaskade_level][upper_level_node].absolute_node_num = SchemeNodeNum;
				scheme[kaskade_level][upper_level_node].absolute_positive_pointer = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].positive_pointer].absolute_node_num;
				scheme[kaskade_level][upper_level_node].absolute_negative_pointer = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].negative_pointer].absolute_node_num;
				scheme[kaskade_level][upper_level_node].variable_number = kaskade_level + 1;
				SchemeNodeNum++;
			}
			if ((scheme[kaskade_level][upper_level_node].to_null != 1) && (scheme[kaskade_level][upper_level_node].fictive_variable == 1))
			{
				scheme[kaskade_level][upper_level_node].absolute_node_num = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].negative_pointer].absolute_node_num;
				scheme[kaskade_level][upper_level_node].variable_number = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].negative_pointer].variable_number;
				scheme[kaskade_level][upper_level_node].absolute_positive_pointer = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].positive_pointer].absolute_positive_pointer;
				scheme[kaskade_level][upper_level_node].absolute_negative_pointer = scheme[kaskade_level+1][scheme[kaskade_level][upper_level_node].negative_pointer].absolute_negative_pointer;
			}
			upper_level_node++;
		}
	}


	//construct cascade scheme matrix
	for(kaskade_level = 0; kaskade_level <5; kaskade_level++)
	{
		upper_level_node = 0;
		while(scheme[kaskade_level][upper_level_node].exist)
		{
			if (scheme[kaskade_level][upper_level_node].fictive_variable != 1)
			{
				SchemeEdgeNum++;
				if (scheme[kaskade_level][upper_level_node].absolute_negative_pointer != -1)
				{
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_negative_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].exist = 1;
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_negative_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].variable_number = scheme[kaskade_level][upper_level_node].variable_number;
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_negative_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].is_inverse = 1;
				}
				if (scheme[kaskade_level][upper_level_node].absolute_positive_pointer != -1)
				{
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_positive_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].exist = 1;
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_positive_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].variable_number = scheme[kaskade_level][upper_level_node].variable_number;
					ContactScheme[scheme[kaskade_level][upper_level_node].absolute_positive_pointer][scheme[kaskade_level][upper_level_node].absolute_node_num].is_inverse = 0;
				}
			}

			upper_level_node++;
		}
	}


	return 0;
}

int main()
{
	FILE * ContactSchemeMatrix;
	ContactSchemeMatrix = fopen("C:\\ContactSchemeMatrix.txt", "w");
	
	int i,j;
	int function[32] = { 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0,
						 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0};

	//int function[32] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	//					 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

	//int function[32] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	//					 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

	for(i = 0; i < 256; i++)
	{
		for(j = 0; j < 256; j++)
		{
			ContactScheme[i][j].exist = 0;
			ContactScheme[i][j].variable_number = -1;
			ContactScheme[i][j].is_inverse = -1;
		}
	}
	
	make_kascade(function);

	fprintf(ContactSchemeMatrix,"Number of nodes: %d\n",SchemeNodeNum);
	fprintf(ContactSchemeMatrix,"Number of edges: %d\n",SchemeEdgeNum);

	fprintf(ContactSchemeMatrix,"  |");
	for(i = 0; i < SchemeNodeNum; i++)
	{
		fprintf(ContactSchemeMatrix,"%d |",i);
	}
	fprintf(ContactSchemeMatrix,"\n");

	for(i = 0; i < SchemeNodeNum; i++)
	{
		fprintf(ContactSchemeMatrix,"%d |",i);
		for(j = 0; j < SchemeNodeNum; j++)
		{
			if (ContactScheme[i][j].exist == 0)
			{
				fprintf(ContactSchemeMatrix,"  ");
			}
			else
			{
				if (ContactScheme[i][j].is_inverse == 1)
				{
					fprintf(ContactSchemeMatrix,"-%d", ContactScheme[i][j].variable_number);
				}
				else
				{
					fprintf(ContactSchemeMatrix," %d", ContactScheme[i][j].variable_number);
				}
			}
			fprintf(ContactSchemeMatrix,"|");
		}
		fprintf(ContactSchemeMatrix,"\n");
	}

	fclose(ContactSchemeMatrix);
	
	return 0;
}